package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;

public class HJ11_最差产品奖 {
    public static void main(String[] args) throws FileNotFoundException {
        MyUtil.START();
        Solution();
        //        Solution2();
        MyUtil.END();
    }

    static void Solution() throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/11.txt"));
        int k = in.nextInt();
        in.nextLine(); // 吸收回车
        String[] sArray = in.nextLine().split(",");
        int N = sArray.length;
        int[] list = new int[N];
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(sArray[i]);
        }
        PriorityQueue<int[]> priorityQueue =
                new PriorityQueue<>(
                        (a, b) -> {
                            return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
                        });
        for (int i = 0; i < k; i++) {
            priorityQueue.add(new int[] {list[i], i});
        }
        int[] resList = new int[N - k + 1];
        resList[0] = priorityQueue.peek()[0];
        for (int i = k; i < N; i++) {
            priorityQueue.add(new int[] {list[i], i});
            if (priorityQueue.peek()[1] <= i - k) {
                priorityQueue.poll();
            }
            resList[i - k + 1] = priorityQueue.peek()[0];
        }
        StringBuilder result = new StringBuilder();
        result.append(resList[0]);
        for (int i = 1; i < N - k + 1; i++) {
            result.append(",").append(resList[i]);
        }
        System.out.println(result);
    }

    static void Solution2() throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/11.txt"));

        int len = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        String[] arr = str.split(",");
        for (int itor = 0; itor < arr.length - len + 1; itor++) {
            int min = 10000;
            if (itor != 0) {
                System.out.print(",");
            }
            for (int inner = 0; inner < len; inner++) {
                int cur = Integer.parseInt(arr[itor + inner]);
                if (min > cur) {
                    min = cur;
                }
            }
            System.out.print(min);
        }
    }
}
